Листинг 19.4. Набросок алгоритма Foil, применяемого для изучения множеств хорновских выражений первого порядка на основе примеров. Функции New-Literals и Choose-Li teral описаны в тексте

Процедура New-Literals выбирает некоторое выражение и составляет все возможные "полезные" литералы, которые могут быть добавлены к этому выражению. Рассмотрим в качестве примера следующее выражение:

К нему могут быть добавлены три описанные ниже разновидности литералов.

1.   Литералы, в которых используются предикаты. Литерал может быть отрицаемым или неотрицаемым, в нем может применяться любой существующий предикат (включая целевой предикат), а все параметры должны быть переменными. В качестве любого параметра предиката может использоваться любая переменная, с учетом одного ограничения: каждый литерал должен включать по меньшей мере одну переменную из предыдущего литерала или из головы выражения. Такие литералы, как Mother (z, и), Married(z,y), Male(у) и Grand fa ther (ν, x), являются допустимыми, a Marri ed(u,v) — нет. Обратите внимание на то, что благодаря имеющейся возможности применять предикат из головы выражения программа Foil может использоваться для изучения рекурсивных определений.

2.   Литералы равенства и неравенства. Эти литералы связывают переменные, уже присутствующие в данном выражении. Например, можно ввести литерал Данные литералы могут также включать константы, заданные пользователем. Для изучения арифметических выражений могут использоваться константы 0 и 1, а для изучения функций, заданных на списках, — пустой список [ ].

3.   Арифметические сравнения. При обработке функций непрерывных переменных могут быть добавлены такие литералы, как х>у и.По аналогии с обучением деревьев решений могут быть выбраны пороговые значения для максимизации различительной мощи проверки.